1. Field of the Invention
The present invention relates to an error correction device, more particularly to an error correction device for cyclic codes.
2. Description of the Related Art
Reed-Solomon (RS) codes are generally used in communication, optical-disc system, high-definition television, etc. When a transmitter transmits an RS code to a receiver, a received signal received by the receiver may have errors and errata due to noise interference during data access and transmission. Therefore, the receiver has to correct the errors and errata of the received signal to thereby obtain original information corresponding to the RS code transmitted by the transmitter.
Before correcting the errors and the errata of the received signal, the receiver has to decode the received signal corresponding to the RS code. Nowadays, many algorithms for decoding the RS code have been proposed. For example, in “Decoding of redundant residue polynomial codes using Euclid's algorithm,” IEEE Trans. On Inf. Theory, Vol. 34, No. 5, pages 1351-1354, September 1988, A. Shiozaki uses the Chinese remainder theorem together with the Euclidean algorithm so as to develop an algorithm for decoding RS codes. However, in view of the complexity of this algorithm, the rate of decoding is relatively slow.
S. V. Fedorenko proposed deriving Gao's algorithm from the Welch-Berlekamp algorithm and the Euclidean algorithm for decoding RS codes in “A simple algorithm for decoding Reed-Solomon codes and its relation to the Welch-Berlekamp algorithm,” IEEE Trans. On Inf. Theory, Vol. 51, No. 3, pages 1196-1198, March 2005. Recently, in “Simplified procedure for decoding nonsystematic Reed-Solomon codes over GF (2m) using Euclid's algorithm and the fast Fourier transform,” IEEE Trans. On Commun., May 2009, T. C. Lin et al. proposed that Gao's algorithm may be extended to correct erasures as well as errors by replacing the initial conditions of the Euclidean algorithm by the erasure-locator polynomial and errata interpolating polynomial. However, use of interpolation substantially increases complexity of the algorithm for decoding RS codes, and thus significantly slows down the rate of decoding.